package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/22
 * @description: 1035. 不相交的线
 * https://leetcode-cn.com/problems/uncrossed-lines/
 * 不相交 VS 子序列的不影响的顺序
 * 那么本题目就是求公共子序列的长度问题
 */
public class B_1035_不相交的线 {

	public static void main(String[] args) {

	}


	public int maxUncrossedLines(int[] A, int[] B) {
		int lenA = A.length;
		int lenB = B.length;
		//B 行 A列
		int[][] dp = new int[lenB][lenA];
		dp[0][0] = A[0] == B[0] ? 1 : 0;
		//处理第一行
		for (int i = 1; i < lenA; i++) {
			if (dp[0][i - 1] == 1 || B[0] == A[i]) {
				dp[0][i] = 1;
			} else {
				dp[0][i] = 0;
			}
		}
		//处理第一列
		for (int i = 1; i < lenB; i++) {
			if (dp[i - 1][0] == 1 || B[i] == A[0]) {
				dp[i][0] = 1;
			} else {
				dp[i][0] = 0;
			}
		}
		//处理后序的
		//dp[i] = max()
		for (int i = 1; i < lenB; i++) {
			for (int j = 1; j < lenA; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (A[j] == B[i]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				} else {
					//dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[lenB - 1][lenA - 1];
	}
}
